package com.sicheng.蓝桥.练习题.dp.数位;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/31 21:09
 */
public class 数字游戏 {

    static final int N = 15;

    static int[][] dp = new int[N][N];

    ///f[i][j]表示最高位是j并且一共有i位的不降数的集合
    static void init() {
        for (int i = 0; i <= 9; i++)
            dp[1][i] = 1;

        for (int i = 2; i < N; i++)
            for (int j = 0; j <= 9; j++)//j要从0开始
                for (int k = j; k <= 9; k++)
                    dp[i][j] += dp[i - 1][k];
    }

    //求 0~n 的不下降数个数
    static int dp(int n) {
        if (n == 0)
            return 1;

        List<Integer> nums = new ArrayList<>();
        while (n > 0) {
            nums.add(n % 10);
            n /= 10;
        }
        int res = 0;//方案数
        int last = 0;//保留一些前缀信息，本题是上一个数是几
        ///从最大数开始枚举
        for (int i = nums.size() - 1; i >= 0; i--) {
            //x为当前这位数
            int x = nums.get(i);
            ////要保障比下一位>=上一位，所以从last开始枚举,最多枚举到x,last为上一位，也即最高位，对下一位的枚举是有限制的
            for (int j = last; j < x; j++)
                ///左端的节点有i+1个位数（因为第一位的下标是0)
                res += dp[i + 1][j];

            //如果当前这位数比上一位小，那么后面的都不成立了，直接break退出
            if (x < last)
                break;

            last = x;

            //如果能顺利到最后一个数说明树的最右边这一段的每一个数都是小于等于前一位数的，因而++
            if (i == 0)
                res++;
        }

        return res;
    }

    //输入
    //1 9
    //1 19
    //输出 9 18
    public static void main(String[] args) {
        init();
        int l, r;
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            l = scanner.nextInt();
            r = scanner.nextInt();
            System.out.println(dp(r) - dp(l - 1));
        }

    }


}
